
class Node{
	int val;
	Node left;
	Node right;
}

// ***************************

public class BTree {

	Node root=new Node();
	
	// ***************************

	public BTree(int a){
		root.val=a;
		root.left=null;
		root.right=null;
	}
	
	// ***************************

	void insert(int a){
		
		findnext(root, a);
	}		

	// ***************************
	
	void findnext(Node n, int a){

		if (a<=n.val){
			if (n.left==null){
				Node newnode = new Node();
				newnode.val=a;
				newnode.left=null;
				newnode.right=null;
				n.left=newnode;
			}
			else
			{ findnext(n.left, a); }
		}	
		else{
			if (n.right==null){
				Node newnode = new Node();
				newnode.val=a;
				newnode.left=null;
				newnode.right=null;
				n.right=newnode;
			}
			else
			{findnext(n.right, a);}
			
		}
	}
	
	// ***************************

	boolean search(Node n, int a){
	
		if (n.val==a){
			return true;
		}
		else
		{
		 if (n.left==null && n.right==null){ return false; }
		 else
		 {
			 if (n.left!=null){return search(n.left,a);}
			 else{
			 if (n.right!=null){return search(n.right,a);}
			 else
			 {return false;}	 
			 }
		 }
		}
	
	}
	
	// ***************************

	void visitInOrder(Node n, String b, int a){
		
		if (n.left==null && n.right==null){
			System.out.println(n.val+b+a);
		}
		else
		{ 
		  if (n.left!=null) {visitInOrder(n.left," left child of ",n.val);}
		  if (n.right!=null) {visitInOrder(n.right," right child of ",n.val);}
		  System.out.println(n.val+b+a);
		}
		
	}
	
	// ***************************
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	BTree myTree = new BTree(7);	
	myTree.insert(3);	
	myTree.insert(1);	
	myTree.insert(12);	
	myTree.insert(2);	
	
	System.out.println("*************************");
	
	myTree.visitInOrder(myTree.root," root ", 0);

	System.out.println("*************************");

	System.out.println(myTree.search(myTree.root,3));
	System.out.println(myTree.search(myTree.root,33));

	}

}
